package leetcode.Hot100;

import leetcode.ListNode;

/**
 * @author Cheng Jun
 * Description: 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * @version 1.0
 * @date 2021/11/28 11:18
 */
public class removeNthFromEnd {

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(1, null);
        ListNode listNode4 = new ListNode(2, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        System.out.println(removeNthFromEnd(listNode4, 2));
    }


    // 双指针
    // 找到 倒数第 n+1 个节点 targetNode，targetNode.next = targetNode.next.next
    static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }
        // 哑节点 dummy
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        int counter = 0;
        while (fast != null) {
            fast = fast.next;
            if (counter < n + 1) counter++;
            else slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    // 还有一种 利用Stack 的方法
    // 还有一种 先找总长度 L，然后根据 n 计算出 应该删除链表中 第 L - n + 1 个节点
}
